class Solution:

    def find_eq(self, nums, value):
        for i in range(len(nums)-1, -1, -1):
            if nums[i] == int(value):
                return nums[i]
        return None

    def find_close_max(self, nums, value):
        for i in range(len(nums)-1, -1, -1):
            if nums[i] < int(value):
                return nums[i]
        return None
    
    def find_max(self, nums):
        return nums[-1]
    
    def gen(self, nums, idx, fix_max=False):
        if idx >= len(self.target):
            return True
        
        if fix_max:
            val = self.find_max(nums)
            self.ans[idx] = val
            return self.gen(nums, idx+1, True)

        val = self.find_eq(nums, self.target[idx])
        # 不能一直是寻找等于的情况，否则会找到等于targe的数字，但是需要找到比target小的最大的数字
        # 所以在最后一个数字时候，需要判断是否全等，如果全等，那么就需要寻找比target小的最大值
        if val is not None and not (self.all_eq and idx == len(self.target)-1):
            self.ans[idx] = val
            ret = self.gen(nums, idx + 1)
            if ret is not None:
                return ret
            else:
                val = self.find_close_max(nums, self.target[idx])
                self.all_eq = False
                if val is not None:
                    self.ans[idx] = val
                    return self.gen(nums, idx + 1, True)
        else:
            val = self.find_close_max(nums, self.target[idx])
            self.all_eq = False
            if val is not None:
                self.ans[idx] = val
                return self.gen(nums, idx + 1, True)
            return None

    
    def maxNumber(self, nums, target):
        nums.sort()
        self.target = list(str(target))
        self.ans = [0 for _ in range(len(self.target))]
        self.all_eq = True

        # 如果第一个数字，无法找到满足条件，那么减少目标值长度，
        # 直接返回最大值，这个要特殊处理。不要老是想着一步到位所有情况
        if self.find_close_max(nums, self.target[0]) == self.find_eq(nums, self.target[0]) == None:
            for i in range(1, len(self.target)):
                self.ans[i] = self.find_max(nums)
        self.gen(nums, 0, 0)
    
        return int(''.join(map(str, self.ans)))


if __name__ == '__main__':
    print("字节1")
    notice = '''
\t给定一个数组，给定一个数字，,用数组中的数字，组成一个最大且小于目标数的数字。
例如给定{2,3,1}, 25632，返回23333'''
    print(notice)

    cases = {
        456: [2, 3, 1],
        25632: [2, 3, 1],
        98765432: [8,2, 3, 1],
        5012: [3, 4, 5],
        1012: [3, 4, 5],
        4111: [3, 4, 5],
        3453: [3, 4, 5],
    }

    for k, v in cases.items():
        s = Solution()
        ans = s.maxNumber(v, k)
        print('case {}, {}: {}'.format(v, k, ans))

